/*
 * @lc app=leetcode.cn id=216 lang=cpp
 *
 * [216] 组合总和 III
 */

// @lc code=start
class Solution
{
private:
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(int k, int n, int index)
    {
        if (path.size() == k && n == 0)
        {
            res.push_back(path);
            return;
        }

        for (int i = index; i <= 9; i++)
        {
            path.push_back(i);
            backtracking(k, n - i, i + 1);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n)
    {
        backtracking(k, n, 1);
        return res;
    }
};
// @lc code=end
